package com.dmall.chapter08.section04;

import com.dmall.chapter02.section09.Graph;

import java.util.ArrayList;

/**
 * @author: xiao1.wang
 * @date: 2022/6/26 21:06
 */
public class FindBridges {
    private Graph G;
    private boolean[] visited;
    private int[] ord;
    private int[] low;
    private int count;

    private ArrayList<Edge> res;

    public FindBridges(Graph G) {
        this.G = G;

        res = new ArrayList<>();

        this.visited = new boolean[G.V()];
        this.ord = new int[G.V()];
        this.low = new int[G.V()];
        this.count = 0;

        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs(v, v);
            }
        }
    }

    private void dfs(int v, int parent) {
        this.visited[v] = true;
        this.ord[v] = count ++;
        this.low[v] = ord[v];
        for (Integer w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w, v);
                low[v] = Math.min(low[v], low[w]);
                if (low[w] > ord[v]) {
                    res.add(new Edge(v, w));
                }
            } else {
                if (w != parent) {
                    low[v] = Math.min(low[v], low[w]);
                }
            }
        }
    }

    public ArrayList<Edge> result() {
        return res;
    }

    public static class Edge {
        private int v1, v2;

        public Edge(int v1, int v2) {
            this.v1 = v1;
            this.v2 = v2;
        }

        @Override
        public String toString() {
            return String.format("%d-%d", v1, v2);
        }
    }

    public static void main(String[] args) {
        String filename1 = FindBridges.class.getClassLoader().getResource("g.txt").getPath();
        Graph g = new Graph(filename1);
        FindBridges fb = new FindBridges(g);
        System.out.println("Bridges in g : " + fb.result());

        String filename2 = FindBridges.class.getClassLoader().getResource("g2.txt").getPath();
        Graph g2 = new Graph(filename2);
        FindBridges fb2 = new FindBridges(g2);
        System.out.println("Bridges in g2 : " + fb2.result());

        String filename3 = FindBridges.class.getClassLoader().getResource("g3.txt").getPath();
        Graph g3 = new Graph(filename3);
        FindBridges fb3 = new FindBridges(g3);
        System.out.println("Bridges in g3 : " + fb3.result());

        String filename4 = FindBridges.class.getClassLoader().getResource("tree.txt").getPath();
        Graph tree = new Graph(filename4);
        FindBridges fb_tree = new FindBridges(tree);
        System.out.println("Bridges in tree : " + fb_tree.result());
    }
}
